/* 
 * File:   arbreCanonique.c
 * Author: thomas
 *
 * Created on 31 mai 2012, 10:39
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include "types.h"
#include "stringutils.h"
#include "constants.h"

/* Insere dans un tableau de letval.
 */
void insererTab(tableau* t, int profondeur, char* lettre) {
    t->tab[(t->nombre)].lettre = lettre;
    t->tab[(t->nombre)].prof = profondeur;
    t->nombre++;
}

/* Parcours l'arbre de huffman en profondeur pour déterminer la profondeur
 * de chaque feuille.
 * @param abr l'arbre de huffman
 * @param tableau le tableau résultat.
 * @param profondeur la profondeur courante dans le parcours
 */
void tableauProfondeur(arbre* abr, tableau* t, int profondeur) {

    if (abr->dte == NULL && abr->gch == NULL) {
        //Feuille
        insererTab(t, profondeur, abr->lettre);
    } else {
        if (abr->dte != NULL) { //Parcours a droite.
            tableauProfondeur(abr->dte, t, profondeur + 1);
        }
        if (abr->gch != NULL) { //Puis a gauche.
            tableauProfondeur(abr->gch, t, profondeur + 1);
        }
    }
}

/* Echange de 2 valeurs d'un tableau de letVal.
 */
void echanger(LetVal* a, LetVal* b) {
    LetVal ech;
    ech = *a;
    *a = *b;
    *b = ech;
}

/* Tri bulles de tableau de LetVal selon leurs profondeurs (ordre croissant)
 *  et leurs lettres (ordre alphabétique).
 * @param le pointeur sur le tableau à trié.
 */
void triBulles(tableau* t) {
    int i, p1, p2, cmp;
    int ordonne = 0;
    int taille = t->nombre;

    while (!ordonne) {
        ordonne = 1; //Ordonné=1 si trié. Donc tant que non trié:
        for (i = 0; i < taille - 1; i++) {
            p1 = t->tab[i].prof;
            p2 = t->tab[i + 1].prof;

            cmp = strcmp(t->tab[i].lettre, t->tab[i + 1].lettre);
            
            if (p1 > p2 || (p1 == p2 && (cmp > 0))) {
                echanger(&(t->tab[i]), &(t->tab[i + 1]));
                ordonne = 0;
            }
        }
        taille--;
    }
}

/*Determine la table des longueurs triées d'un arbre de huffman.
 * @return la table des longueur
 * @param Un arbre de Huffman
 */
tableau* tableLongueur (arbre* huff){
    tableau* t = malloc(sizeof(tableau));
    t->nombre = 0;
    t->tab=(LetVal*) calloc(TAILLE_DICTIONNAIRE, sizeof (LetVal));
    tableauProfondeur(huff,t,0);
    triBulles(t);
    return t;
}

/* Genere un codage pour chaque caractère à partir d'un tableau de longueur.
 * @param le tableau des longueur.
 * @return le tableau résultat.
 */
LongCod* creerCodage(tableau* t) {
    LongCod* lc = (LongCod*) calloc(TAILLE_DICTIONNAIRE, sizeof (LongCod));
    long long int premier = 0;
    int  i=0; 
    int prof = 0;

    while (i < t->nombre) {
        if (prof == t->tab[i].prof) {
            lc[(unsigned char)t->tab[i].lettre[0]].longeur = prof;
            lc[(unsigned char)t->tab[i].lettre[0]].code = premier;
            premier++;
            i++;
        } else {
            prof++;
            premier=premier*2;
        }
    }
    return lc;
}

/* Genere un codage pour chaque caractère à partir d'un arbre de Huffman.
 * @param l'arbre de Huffman.
 * @return le tableau résultat.
 */
LongCod* genererCode (arbre* huff){
    return (creerCodage(tableLongueur(huff)));
}